package com.dyz.leetcode._20_dynamicProgramming._139;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class wordBreak02 {
    private HashMap<Integer, Boolean> map = new HashMap<>();
    public boolean wordBreak(String s, List<String> wordDict) {
        return dfs(s, 0, new HashSet<>(wordDict));

    }
    private boolean dfs(String s, int i, Set<String> wordDict){
        if(i==s.length()){return true;}
        if(map.containsKey(i)){return map.get(i);}
        for (int end = i+1; end <= s.length(); end++) {
            if(!wordDict.contains(s.substring(i, end))){continue;}
            boolean flag = dfs(s, end, wordDict);
            if (flag){
                map.put(i, true);
                return true;
            }
        }
        map.put(i, false);
        return false;
    }
}
